# ----------------------------------------------
# Project： calculate diameter of graph
# Using floyd algorithm
# ----------------------------------------------
import pandas as pd

# define function: print shortest path
def getPath(i, j):
    if i != j:
        if path[i][j] == -1:
            print('-', j+1, end='')
        else:
            getPath(i, path[i][j])
            getPath(path[i][j], j)


def printPath(i, j):
    print(' Path:', i+1, end='')
    getPath(i, j)
    print()


data = [[1, 5, 30],
        [1, 13, 50],
        [1, 21, 70],
        [1, 2, 20],
        [1, 20, 183],
        [1, 12, 203],
        [1, 4, 223],
        [2, 1, 20],
        [2, 3, 20],
        [3, 2, 20],
        [3, 4, 20],
        [4, 3, 20],
        [4, 12, 43],
        [4, 20, 63],
        [4, 21, 173],
        [4, 13, 193],
        [4, 5, 213],
        [4, 1, 223],
        [5, 6, 20],
        [5, 13, 40],
        [5, 21, 60],
        [5, 20, 173],
        [5, 12, 193],
        [5, 4, 213],
        [6, 5, 20],
        [6, 7, 20],
        [7, 6, 20],
        [7, 8, 20],
        [8, 7, 20],
        [9, 10, 20],
        [10, 9, 20],
        [10, 11, 20],
        [11, 10, 20],
        [11, 12, 20],
        [12, 11, 20],
        [12, 4, 43],
        [12, 20, 43],
        [12, 21, 153],
        [12, 13, 173],
        [12, 5, 173],
        [12, 1, 183],
        [13, 14, 20],
        [13, 5, 40],
        [13, 1, 50],
        [13, 21, 40],
        [13, 20, 153],
        [13, 12, 173],
        [13, 4, 193],
        [14, 13, 20],
        [14, 15, 20],
        [15, 14, 20],
        [15, 16, 20],
        [16, 15, 20],
        [17, 18, 20],
        [18, 17, 20],
        [18, 19, 20],
        [19, 18, 20],
        [19, 20, 20],
        [20, 19, 20],
        [20, 12, 43],
        [20, 4, 63],
        [20, 21, 133],
        [20, 13, 153],
        [20, 5, 173],
        [20, 1, 183],
        [21, 22, 20],
        [21, 13, 40],
        [21, 5, 60],
        [21, 1, 70],
        [21, 20, 133],
        [21, 12, 153],
        [21, 4, 173],
        [22, 21, 20],
        [22, 23, 20],
        [23, 22, 20],
        [23, 24, 20],
        [24, 23, 20],
        [49, 4, 11.5],
        [49, 12, 31.5],
        [49, 20, 51.5],
        [49, 21, 161.5],
        [49, 13, 181.5],
        [49, 5, 201.5],
        [49, 1, 211.5],
        [4, 49, 11.5],
        [12, 49, 31.5],
        [20, 49, 51.5],
        [21, 49, 161.5],
        [13, 49, 181.5],
        [5, 49, 201.5],
        [1, 49, 211.5],
        [25, 29, 30],
        [25, 37, 50],
        [25, 45, 70],
        [25, 26, 20],
        [25, 44, 183],
        [25, 36, 203],
        [25, 28, 223],
        [26, 25, 20],
        [26, 27, 20],
        [27, 26, 20],
        [27, 28, 20],
        [28, 27, 20],
        [28, 36, 43],
        [28, 44, 63],
        [28, 45, 173],
        [28, 37, 193],
        [28, 29, 213],
        [28, 25, 223],
        [29, 30, 20],
        [29, 37, 40],
        [29, 45, 60],
        [29, 44, 173],
        [29, 36, 193],
        [29, 28, 213],
        [30, 29, 20],
        [30, 31, 20],
        [31, 30, 20],
        [31, 32, 20],
        [32, 31, 20],
        [33, 34, 20],
        [34, 33, 20],
        [34, 35, 20],
        [35, 34, 20],
        [35, 36, 20],
        [36, 35, 20],
        [36, 28, 43],
        [36, 44, 43],
        [36, 45, 153],
        [36, 37, 173],
        [36, 29, 173],
        [36, 25, 183],
        [37, 38, 20],
        [37, 29, 40],
        [37, 25, 50],
        [37, 45, 40],
        [37, 44, 153],
        [37, 36, 173],
        [37, 28, 193],
        [38, 37, 20],
        [38, 39, 20],
        [39, 38, 20],
        [39, 40, 20],
        [40, 39, 20],
        [41, 42, 20],
        [42, 41, 20],
        [42, 43, 20],
        [43, 42, 20],
        [43, 44, 20],
        [44, 43, 20],
        [44, 36, 43],
        [44, 28, 63],
        [44, 45, 133],
        [44, 37, 153],
        [44, 29, 173],
        [44, 25, 183],
        [45, 46, 20],
        [45, 37, 40],
        [45, 29, 60],
        [45, 25, 70],
        [45, 44, 133],
        [45, 36, 153],
        [45, 28, 173],
        [46, 45, 20],
        [46, 47, 20],
        [47, 46, 20],
        [47, 48, 20],
        [48, 47, 20],
        [49, 25, 10],
        [49, 29, 20],
        [49, 37, 40],
        [49, 45, 60],
        [49, 44, 173],
        [49, 36, 193],
        [49, 28, 213],
        [25, 49, 10],
        [29, 49, 20],
        [37, 49, 40],
        [45, 49, 60],
        [44, 49, 173],
        [36, 49, 193],
        [28, 49, 213],
        [50, 49, 10],
        [50, 29, 10],
        [50, 51, 10],
        [49, 50, 10],
        [29, 50, 10],
        [51, 50, 10],
        [51, 12, 11.5],
        [51, 52, 10],
        [12, 51, 11.5],
        [52, 51, 10],
        [52, 37, 10],
        [52, 53, 10],
        [37, 52, 10],
        [53, 52, 10],
        [53, 20, 11.5],
        [53, 54, 10],
        [20, 53, 11.5],
        [54, 53, 10],
        [54, 45, 10],
        [54, 44, 123],
        [54, 36, 143],
        [54, 28, 163],
        [54, 21, 111.5],
        [54, 13, 131.5],
        [54, 5, 151.5],
        [54, 1, 161.5],
        [45, 54, 10],
        [44, 54, 123],
        [36, 54, 143],
        [28, 54, 163],
        [21, 54, 111.5],
        [13, 54, 131.5],
        [5, 54, 151.5],
        [1, 54, 161.5]
        ]


print('---------------- Program start ----------------')
# read data
flag = 2
vertex = 54
edge = len(data)


# initialized

inf = 99999999
dis = []  # matrix of the shortest distance
path = []  # record the shortest path
for i in range(vertex):
    dis += [[]]
    for j in range(vertex):
        if i == j:
            dis[i].append(0)
        else:
            dis[i].append(inf)
for i in range(vertex):
    path += [[]]
    for j in range(vertex):
        path[i].append(-1)


# read weight information
for i in range(edge):
    u, v, w = data[i][0], data[i][1], data[i][2]
    u, v, w = int(u)-1, int(v)-1, int(w)
    if flag == 1:
        dis[u][v] = w
    elif flag == 2:
        dis[u][v] = w
        dis[v][u] = w
print('the weight matrix is:')
for i in range(vertex):
    for j in range(vertex):
        if dis[i][j] != inf:
            print('%5d' % dis[i][j], end='')
        else:
            print('%5s' % '∞', end='')
    print()


# floyd algorithm
for k in range(vertex):
    for i in range(vertex):
        for j in range(vertex):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]
                path[i][j] = k
print('===========================================')


test = pd.DataFrame(dis)
test.to_csv('new_data2.csv', encoding='utf-8')
# output the result
print('output the result:')
# max(max(dis)): the max item of two dimension matrix
print('>> the diameter of graph: %d <<' % max(max(dis)))
print('-------------- Program end ----------------')